public enum InsertionSort implements Sort {
    INSTANCE;

    /**
     * 插入排序 v1版本，性能差
     *
     * @param arr
     * @param <E>
     */
    public <E extends Comparable<E>> void sortV1(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    SortingHelper.INSTANCE.swap(arr, j, j + 1);
                }
            }
        }
    }

    /**
     * 性能提高约1/3
     *
     * @param arr
     * @param <E>
     */
    public <E extends Comparable<E>> void sortV2(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
//            for (int j = i - 1; j >= 0; j--) {
//                if (arr[j].compareTo(arr[j + 1]) > 0) {
//                    SortingHelper.INSTANCE.swap(arr, j, j + 1);
//                } else {
//                    break;
//                }
//            }
            for (int j = i - 1; j >= 0 && arr[j].compareTo(arr[j + 1]) > 0; j--) {
                SortingHelper.INSTANCE.swap(arr, j, j + 1);
            }
        }
    }

    /**
     * arr[0,i)已经排序，arr[i,n)未排序    循环不变量
     *
     * @param arr
     * @param <E>
     */

    public <E extends Comparable<E>> void sort1(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            E temp = arr[i]; //暂存arr[i]
            int j; //寻找temp实际应该存放的位置
            //循环结束后，j位置存放的就应该是temp插入的位置
            for (j = i; j - 1 >= 0 && temp.compareTo(arr[j - 1]) < 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }

    /**
     * arr[i,n)已排序，arr[0,i)未排序  循环不变量
     * 从后向前扫描，对于每一个arr[i],寻找arr[i..n)区间中需要插入的位置。
     * 具体在找这个位置的时候，我们依然是暂存arr[i]到t这个变量中。之后，只要t比当前的arr[j+1]还要大，说明t应该插入的位置还要靠后，我们只需要让arr[j+1]平行移动到arr[j]
     * 的位置，然后j++，继续看下一个j
     * <p>
     * 在sort1中，我们从前向后，每次对于某一个arr[i],在前面找到其插入的位置；
     * 在sort中，我们从后向前，每次对于某一个arr[i],在后面找到其插入的位置。
     *
     * @param arr
     * @param <E>
     */
    @Override
    public <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = arr.length - 1; i >= 0; i--) {
            E temp = arr[i];
            int j;
            for (j = i; j + 1 < arr.length && temp.compareTo(arr[j + 1]) > 0; j++) {
                arr[j] = arr[j + 1];
            }
            arr[j] = temp;
        }
    }
}
